package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/6/15 22:59
 */
public class Rob3_337 {

    /**
     * 问题的核心在于分成两组值进行比较（想到了）。难点是如何实现间隔遍历（没想到）
     *
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        // 简易记忆化搜索！掌握
        // 记忆化遍历 -- 注意记录研途根节点的值，防止重复遍历
        return rob(root, new HashMap<>());
    }

    public int rob(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null) return 0;
        // 如果已经遍历过这个结点，那么直接返回节点的值
        if (memo.containsKey(root)) return memo.get(root);
        int first = rob(root.left, memo) + rob(root.right, memo);
        int second = root.val;
        if (root.left != null) {
            second += rob(root.left.left, memo) + rob(root.left.right, memo);
        }
        if (root.right != null) {
            second += rob(root.right.left, memo) + rob(root.right.right, memo);
        }
        int result = Math.max(first, second);
        // 将最大值添加到memo中
        memo.put(root, result);
        return result;
    }

    // 基于动态规划的记忆化搜索
    public int[] robInternal(TreeNode root) {
        int[] result = new int[2];
        if (root != null) {
            // 获得左右子树的结果
            int[] left = robInternal(root.left);
            int[] right = robInternal(root.right);
            // 0 表示不偷根节点，那么可以选择下一个偷或不偷的最大值
            result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            // 1 表示偷根节点
            result[1] = left[0] + right[0] + root.val;
        }
        return result;
    }

    public int rob(Map<TreeNode, Integer> memo, TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int left1 = 0 , left2 = 0, right1 = 0, right2 = 0;
        if (root.left != null) {
            left1 = root.left.val;
            left2 = rob(memo, root.left.left) + rob(memo, root.left.right);
        }
        if (root.right != null) {
            right1 = root.right.val;
            right2 = rob(memo, root.right.left) + rob(memo, root.right.right);
        }
        int result = Math.max(left1 + right1, root.val + left2 + right2);
        memo.put(root, result);
        return result;
    }

    static class Solution {
        public int rob(TreeNode root) {
            return rob(root, new HashMap<>());
        }

        public int rob(TreeNode root, Map<TreeNode, Integer> memo) {
            if (root == null) return 0;
            if (memo.containsKey(root)) return memo.get(root);
            int first = root.val, second;
            second = rob(root.left, memo) + rob(root.right, memo);
            if (root.left != null) first += rob(root.left.left, memo) + rob(root.left.right, memo);
            if (root.right != null) first += rob(root.right.left, memo) + rob(root.right.right, memo);
            int res = Math.max(first, second);
            memo.put(root, res);
            return res;
        }

        public int rob2(TreeNode root) {
            int[] res = robInterval(root);
            return Math.max(res[0], res[1]);
        }

        private int[] robInterval(TreeNode root) {
            int[] rob = new int[2];
            if (root != null) {
                int[] left = robInterval(root.left);
                int[] right = robInterval(root.right);
                rob[0] = root.val + left[1] + right[1];
                // 如果不偷根节点，那么可以选择两者的最大值进行相加
                rob[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            }
            return rob;
        }

    }

}
